#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
	
};

class Solution {
public:
	ListNode* sortList(ListNode* head) {
		if (!head) return NULL;
		vector<int> list;
		ListNode* h = head;
		while (h) {
			list.push_back(h->val);
			h = h->next;
		}
		sort(list.begin(), list.end());
		ListNode *newhead=new ListNode();
		newhead->val = list[0];
		ListNode *r = newhead;
		for (int i = 1; i < list.size(); i++) {
			ListNode *t=new ListNode();
			t->val = list[i];
			r->next =t;
			r = t;
		}
		return newhead;
	}
};

int main() {
	Solution s;
	ListNode n1(1), n2(2), n3(3), n4(4);
	n1.next = &n3, n3.next = &n2, n2.next = &n4;
	s.sortList(&n1);
}